\documentclass[letterpaper,onecolumn,10pt]{article}
\usepackage{graphicx}
\usepackage{algorithmicx}
\usepackage{algpseudocode}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage[usenames,dvipsnames]{color}
\usepackage{hyperref}
\usepackage{tikz}
\usepackage{pgfplots}
\usetikzlibrary{matrix,shapes,decorations}
\usepackage{array}
\usepackage{parskip}
\newcolumntype{L}[1]{>{\raggedright\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}
\newcolumntype{C}[1]{>{\centering\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}
\newcolumntype{R}[1]{>{\raggedleft\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}

% Define root path
%\def \ROOTPATH {/Users/harper/Repositories/research-papers-hao/ip-geolocation/}
\def \ROOTPATH {/home/harper/Repositories/research-papers-hao/ip-geolocation/}


\graphicspath{\ROOTPATH{image/}}

\begin{document}
\date{}

\title{\Large \bf Enhanced Traceroute}

% For pdflatex
\setlength{\pdfpagewidth}{8.5in}
\setlength{\pdfpageheight}{11in}

% Copy setting from USENIX
\setlength{\textheight}{9.0in}
\setlength{\columnsep}{0.25in}
\setlength{\textwidth}{6.50in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}

\setlength\parindent{0pt}
\setlength\parskip{4px}

%for single author (just remove % characters)
\author{
{\rm Hao Jiang}\\
Clarkson University
\and
{\rm Jeanna N. Matthews}\\
Clarkson University
% copy the following lines to add more authors
% \and
% {\rm Name}\\
%Name Institution
} % end author

\maketitle


%--------------------------------------------------------------------
\section*{Proposal}

I want to design a enhanced version of traceroute, that can detect information about anonymous routers. Current traceroute works by sending IP packet with TTL from 1 to some large number to destination. When a intermediate route receive a packet and decrease TTL, if the TTL is already 0, the packet is dropped and a ICMP expire response will be sent back to the source. Hence a intermediate hop is found.

However, some routers choose not to respond to an ICMP when receiving a packet with TTL = 0. In such cases, the source will wait until timeout and record a ``*'' in the traceroute result. My goal is to find out the IP and delay information to these intermediate routers. We call these routers anonymous routers or hidden ones. Our goal is to discover these hidden ones and provide a complete traceroute information.

\begin{figure}[h]
\begin{tikzpicture}
[
	router/.style={circle, draw=black!50, fill=blue!20, minimum size = 6mm},
	point/.style={rectangle, draw=black!50, fill=yellow!30, rounded corners,minimum width = 2.5cm, minimum height=0.8cm},
	output/.style={rectangle, draw=black!50, fill=red!20, rounded corners,minimum width = 0.7cm, minimum height=6mm},
	target/.style={rectangle, draw=black!50, fill=green!20, rounded corners,minimum width = 0.8cm, minimum height=0.8cm}
]
\matrix[matrix of nodes,
column sep={1cm},
row sep={0.5cm}] {
& \node[router](router-1){}; && \node[router](router-2){}; & \\
\node[point](source){Source}; && & & \node[point](dest){Dest}; \\
& \node[router](router-3){}; && \node[router](router-4){}; & \\
};

\draw(source.east)--(router-1);
\draw(router-1)--(router-2);
\draw(router-2)--(router-3);
\draw(router-3)--(router-4);
\draw(router-4)--(dest.west);

\node[below left] at (router-3.west){No ICMP};
\end{tikzpicture}

\vspace{0.5cm}

\begin{tabular}{l l l l} 
Router 1 & 1ms & 1ms & 1ms\\
Router 2 & 1ms & 1ms & 1ms\\
&* & *  &*\\
Router 4 & 10ms & 8ms & 9ms\\
Dest & 10ms & 11ms & 14ms\\
\end{tabular}
\caption{Demonstrate of Traceroute}
\label{}
\end{figure}

To achieve this, we make use of IP options. Record Route (RR) and Time Stamp (TS). Detail information of these two options can be found in RFC 791(Pg. 20-22). Basically, RR allows the packet to record at most 9 IP address it passes through. TS allows the packet to record the timestamp on at most 4 prespecified IP addresses in sequence. 

Our first step is to figure out IP addresses for the anonymous routers. We first use RR to directly get IP addresses that is within 9 hops of our source.  For those who are out of 9 hops, we use Internet Topology platform such as iPlane and CAIDA data to look for possible candidates. These candidates are then verified using TS option. Assume we are currently with point $s$, and the next known IP in this path is $d$. For a candidate $c$, we can verify it by sending a packet from to $d$, with IP option set to TS $\{s,c,d\}$. We then check the returned packet to see whether all the TS information had been filled up. If so, $c$ is the next one on the path list. We keep trying until we reach the destination. The algorithm is described as in \ref{algorithm}.

\begin{figure}
\centering
\begin{tikzpicture}
[
	router/.style={circle, draw=black!50, fill=blue!20, minimum size = 6mm},
	center/.style={circle, draw=black!50, fill=yellow!40, minimum size = 6mm},
	point/.style={rectangle, draw=black!50, fill=yellow!30, rounded corners,minimum width = 2.5cm, minimum height=0.8cm},
	hrouter/.style={circle, dashed, draw=black!50, fill=red!20, minimum size = 6mm},
	target/.style={rectangle, draw=black!50, fill=green!20, rounded corners,minimum width = 0.8cm, minimum height=0.8cm}
]
\matrix[
matrix of nodes,
column sep={1cm},
row sep={0.5cm}
] {
& \node[router](router-1){}; &\node[router](router-2){};& \node[hrouter](router-3){}; & \\
\node[point](source){Source}; &&\node[router](router-4){}; & & \node[point](dest){Dest}; \\
& \node[hrouter](router-5){}; &\node[hrouter](router-6){};& \node[hrouter](router-7){}; & \\
};

\draw(source.east)--(router-1);
\draw(router-1)--(router-2);
\draw(router-2)--(router-3);
\draw(router-3)--(router-4);
\draw(router-4)--(router-5);
\draw(router-5)--(router-6);
\draw(router-6)--(router-7);
\draw(router-7)--(dest.west);

\node[above] at (router-2.north) {R2};
\node[right] at (router-4.east) {R4};
\end{tikzpicture}

\vspace{0.5cm}

\begin{tikzpicture}
[
	router/.style={circle, draw=black!50, fill=green!20, minimum size = 6mm},
	center/.style={circle, draw=black!50, fill=yellow!40, minimum size = 6mm},
	point/.style={rectangle, draw=black!50, fill=yellow!30, rounded corners,minimum width = 2.5cm, minimum height=0.8cm},
	hrouter/.style={circle, dashed, draw=black!50, fill=red!20, minimum size = 6mm},
	target/.style={rectangle, draw=black!50, fill=green!20, rounded corners,minimum width = 0.8cm, minimum height=0.8cm}
]
\matrix[
matrix of nodes, 
column sep={0.5cm},
row sep={0.5cm}
] {
\node[router](router-1){}; & \node[router](router-2){}; & \node[router](router-3){};\\
\node[router](router-4){}; & \node[center](center){R2}; & \node[router](router-5){};\\
\node[router](router-6){}; & \node[router](router-7){}; & \node[router](router-8){};\\
};

\node[right](hint) at (router-5.east) {Adjancent Routers};

\foreach \x in {1,...,8} {
	\draw(center)--(router-\x);
}


\end{tikzpicture}
\caption{IP discovering Demo}
\label{ip_discovering}
\end{figure}


\begin{figure}[t]
\begin{algorithmic}
\While {$i \neq dest$} 
      \If {$i.known\_ip$}
      	   \State $i\gets i+1$
      	   \State \textbf{continue}
      \EndIf
      \State $s \gets i-1$
      \State $n \gets i+1$
      \While {! $n.known\_ip$}
      	\State $n \gets n +1$
      \EndWhile
      
      \For {$t \in s.adjList$}
      	   \If {\Call {is\_between}{$s,t,n$}}
      		\State $i.ip \gets t.ip$
      		\State $i.known\_ip \gets true$
      		\State \textbf{break}
      	   \EndIf
      \EndFor
\EndWhile
\\
\Function{is\_between}{$s,t,n$}
    \State \text{Send Packet with TS option: $s,t,n$}
    \If {\text{All TS info is filled}}
    	\State \Return $true$
    \Else
    	\State \Return $false$
    \EndIf
\EndFunction
\end{algorithmic}
\caption{Algorithm}
\label{algorithm}
\end{figure}
Once we confirms the IP address of these hidden routers, we will know the IP address of target nodes, and we further issue a packet with TS option to get its local timestamp. We can safely assume that all these routers have their local timestamp synchronized with a time server. Thus by subtracting the recorded timestamp with the time we sent out this packet, we know a single trip time. RTT can be retrieved by duplicating it. We can also adept similar idears as is described in Ethan's \textit{Reverse Traceroute} to get a more accurate RTT value.

\section*{Possible Problems and Error Recovery}

One problem is that some routers may not support IP option. We are doomed in that case. However, in our research we can see how many routers actually ignore IP options. As Ethan's method also is based on similar idea, we can safely assume that this is not the majority.

The biggest problem I may encounter in this research is that CAIDA doesn't provide enough information about adjancent routers. CAIDA's data is basically based on normal traceroute, which doesn't provide anonymous route information. iPlane claims that they can provide this information by issuing RR from different PlanetLab nodes and discover routers within 9 hops from them. We could do similar things if their result is not good enough for us. However, this requires access to PlanetLab. Maybe we can borrow a PlanetLab account from someone?

Is this paper not innovative enough? This is a possible criticism because our method is almost the same as Ethan's \textit{Reverse Traceroute}. We just make use of the timestamp information they ignore. However, we do solve the problem ignored by others.  I don't think I can answer this question.

\end{document}